package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/'>有序链表转换二叉搜索树(Convert Sorted List to Binary Search Tree)</a>
 * <p>给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。</p>
 * <p>本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: head = [-10,-3,0,5,9]
 *          -10 -> -3 -> 0 -> 5 -> 9
 *      输出: [0,-3,9,-10,null,5]
 *                  0
 *                /  \
 *              -3    9
 *             /     /
 *           -10    5
 *      解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
 *
 * 示例 2:
 *      输入: head = []
 *      输出: []
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>head 中的节点数在[0, 2 * 10^4] 范围内</li>
 *     <li>-10^5 <= Node.val <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/16 11:23
 */
public class LC0109ConvertSortedListToBinarySearchTree_M {

    static class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            //递归每次选取链表的中间节点作为根节点构造树
            if(head == null){
                return null;
            }
            if (head.next == null) {
                return new TreeNode(head.val);
            }
            // 找到链表的中间节点，作为树的根节点。中间节点的前面的链表，作为左子树；中间节点后面的链表，作为右子树
            ListNode slow = head;
            ListNode fast = head;
            ListNode prev = null;
            while (fast != null && fast.next != null) {
                prev = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            // 此时 prev 位于第一段链表的尾； slow 位于中间节点。断开链表
            prev.next = null;

            TreeNode root = new TreeNode(slow.val);
            root.left = sortedListToBST(head);
            root.right = sortedListToBST(slow.next);
            return root;
        }

        /**
         * 先将有序链表转换成有序数组，方便每次找到中间节点
         */
        public TreeNode sortedListToBST2(ListNode head) {
            List<Integer> nums = new ArrayList<>();
            while (head != null) {
                nums.add(head.val);
                head = head.next;
            }
            return buildBST(nums, 0, nums.size() - 1);
        }

        private TreeNode buildBST(List<Integer> nums, int start, int end) {
            if (start > end) {
                return null;
            }
            int mid = (start + end) >> 1;
            TreeNode root = new TreeNode(nums.get(mid));
            root.left = buildBST(nums, start, mid - 1);
            root.right = buildBST(nums, mid + 1, end);
            return root;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode head = new ListNode(-10);
        head.next = new ListNode(-3);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(5);
        head.next.next.next.next = new ListNode(9);
        TreeNode.printTree(solution.sortedListToBST(head));
    }
}
